#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include "utils.h"
using namespace std;

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder){
        if (!preorder.size() || !inorder.size()) return NULL;
        TreeNode *root = new TreeNode(preorder[0]);
        vector<int>::iterator it = find(inorder.begin(), inorder.end(), preorder[0]);
        int len = it - inorder.begin();
        root->left = build(preorder.begin()+1, preorder.begin()+len+1, inorder.begin(), it);
        root->right = build(preorder.begin()+len+1, preorder.end(), it+1, inorder.end());
        return root;
    }

    TreeNode *build(vector<int>::iterator pre_beg, vector<int>::iterator pre_end, vector<int>::iterator in_beg, vector<int>::iterator in_end){
        if (pre_beg == pre_end) {
            return NULL;
        }
        TreeNode *root = new TreeNode(*pre_beg);
        vector<int>::iterator it = find(in_beg, in_end, *pre_beg);
        int len = it - in_beg;
        root->left = build(pre_beg+1, pre_beg+len+1, in_beg, it);
        root->right = build(pre_beg+len+1, pre_end, it+1, in_end);
        return root;
    }

    TreeNode *build(vector<int>::iterator pre_beg, vector<int>::iterator in_beg, int size){
        if (!size) {
            return NULL;
        }
        TreeNode *root = new TreeNode(*pre_beg);
        vector<int>::iterator it = find(in_beg, in_beg+size, *pre_beg);
        int left_len = it - in_beg;
        int right_len = size - left_len - 1;
        root->left = build(pre_beg+1, in_beg, left_len);
        root->right = build(pre_beg+left_len+1, it+1, right_len);
    }
};

int main(int argc, char *argv[])
{
    //int pre[] = {1,2,4,3,5,6}, in[] = {4,2,1,5,3,6};
    int pre[] = {1,3,5,6}, in[] = {1,5,3,6};
    vector<int> preorder(pre, pre+sizeof(pre)/sizeof(int));
    vector<int> inorder(in,in+sizeof(in)/sizeof(int));

    Solution ss;
    print_vector(levelOrder(ss.buildTree(preorder, inorder)));

    return 0;
}
